1. Field of the Invention
The present invention relates to an apparatus and a method for processing uni- and multi-dimensional discrete signals such as audio, radar, sonar, natural images, photographs, drawings, multi-spectral images, volumetric medical image data sets, video sequences, etc. It further relates to the processing of such signals, images, video, and other multi-dimensional signals which are captured directly in digital format or after they have been converted to or expressed in digital format. This invention further relates to use of fast and efficient reconstruction methods to increase the processing speed for digital signal storage and transmission, especially in fixed-point hardware implementations. More particularly, the present invention relates to the processing of image/video data.
2. Description of the Related Art
Invertible transformations, especially unitary ones, have been in frequent use in signal processing for decades, for both their energy compaction as well as signal analysis benefits, Perhaps the most common example is the Fast Fourier Transform, and its various close relatives. The discrete cosine transform (DCT), a well-known such relative, which is in fact an orthogonal transformation of sets of real-valued coefficients, has been at the heart of the algorithmic structure of many international standards such as JPEG, H.26x, and the MPEG family of standards, as discussed for example in J. Mitchell, W. Pennebaker, C. Fogg, and D. LeGall, MPEG Video Compression Standard, Chapman and Hall, New York, 1996. It has satisfactory performance in terms of signal energy compaction capability, and many fast algorithms for the DCT and its inverse transform, the so-called IDCT, have been proposed. One type of the fast algorithms is based on various sparse factorizations of the DCT/IDCT matrix such as Chen's factorization in W. Chen, C. Harrison, and S. Fralick, “A fast computational algorithm for the discrete cosine transform,” IEEE Trans. Communications, vol. COM-25, pp. 1004.1011, 1977 and Loeffler's factorization as in C. Loeffler, A. Lightberg, and G. Moschytz, “Practical fast 1-D DCT algorithms with 11 multiplications,” in Proc. IEEE ICASSP, vol. 2, pp. 988-991, 1989. To achieve fast implementations, floating-point coefficients in these algorithms are usually scaled and approximated by integers such that floating-point multiplications in DCT/IDCT can be replaced by integer multiplications, and potentially with only additions and bitshifts.
The use of fixed-point DCT/IDCT implementations results in approximation errors when compared with the ideal DCT/IDCT. Until recently, existing standards such as MPEG-1, 2, 4, have required that all approximate IDCTs meet certain accuracy requirements (the IEEE-1180 Standard, see below) to the true floating point IDCT. As different video/image decoders have the freedom to employ different IDCT fixed-point approximations, it leads to the mismatched reconstruction of the decoded frame relative to the encoder's model of the intended decoded picture. Subsequent inter-picture prediction from the aforementioned mismatched P-frame results in error accumulation and generates the so-called drifting effects. Annoying drifting problems can degrade decoded video quality quickly, especially when the encoder has a minimal amount of intra-block refresh.
Recently, MPEG has embarked on an effect to develop a new voluntary standard specifying a particular fixed-point approximation to the ideal IDCT function, and has a call for proposals on fixed-point 8×8 IDCT and DCT Standards in G. Sullivan and A. Luthra, “Call for proposals on fixed-point 8×8 IDCT and DCT standard,” MPEG input contribution N7099, April 2005. This Call for Proposals (CfP) requires an approximation that is within a specified degree of precision relative to the ideal function definition of the IDCT. And the accuracy requirements are compliant to the now-obsolete IEEE-1180 standard described in IEEE CAS Standards Committee, “IEEE standard specification for the implementation of 8×8 inverse discrete cosine transform,” IEEE Standard 1180-1990, December 1990, which has specified a set of well-known evaluation criteria for the accuracy of fixed-point IDCT implementations. The more recent ISO/IEC MPEG 23002-1 Standard, “Accuracy requirements for implementation of integer-output 8×8 inverse discrete cosine transform,” which is effectively identical, now replaces this standard; however, since the IEEE-1180 tests are still better known, we will continue to refer to them. In reality, the new MPEG 23002-1 Standard is implied.
Generally, a fixed-point IDCT algorithm implemented within a wider data bus width (e.g., the number of bits of representation needed for the transformation process) can have higher approximation accuracy than one with a lower bus width. However, the added data bus width is costly in VLSI implementation, and especially in mobile devices, where the CPU capability, bus width, and battery power are severely limited.
In the field of fixed-point IDCT designs (such as two fast algorithms in the public-domain JPEG source code), irrational multiplication parameters are directly scaled up and then approximated as the nearest integers, often suffering from poor approximation accuracy despite very high parameter resolution.
Therefore, it is an object of this invention to provide high-accuracy approximations of the IDCT that can still be implemented with a narrow bus width via simple arithmetic operations such as shifting operations and binary additions. It is a further object of this invention to provide a method of constructing useful alternative representations and approximations of invertible transforms.
The current invention is related to the invention disclosed in the Reissue U.S. patent application Ser. No. 10/629,303 of U.S. Pat. No. 6,421,464, to Trac D. Tran and Pankaj Topiwala, both of which are hereby incorporated by reference in the entirety.